#ifndef REVERSED_ITERATOR
#define REVERSED_ITERATOR
// 将一个顺序访问的迭代器包装成反向迭代器
template<typename TSequentialAccessIterator>
class ReversedSequentailAccessIterator
{
private:
	TSequentialAccessIterator* pIterator;
public:
	ReversedSequentailAccessIterator(TSequentialAccessIterator& it);
	ReversedSequentailAccessIterator(const ReversedSequentailAccessIterator& other);
	~ReversedSequentailAccessIterator();
public:
	using ValueType = typename TSequentialAccessIterator::ValueType;
	// 前置++
	ReversedSequentailAccessIterator& operator++() noexcept;
	// 前置--
	ReversedSequentailAccessIterator& operator--() noexcept;
	bool operator==(const ReversedSequentailAccessIterator& other) const noexcept;
	bool operator!=(const ReversedSequentailAccessIterator& other) const noexcept;
	ValueType& operator*();
	ValueType* operator->();
	operator TSequentialAccessIterator();
};

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::ReversedSequentailAccessIterator(TSequentialAccessIterator& it)
{
	this->pIterator = new TSequentialAccessIterator(it);
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::ReversedSequentailAccessIterator(const ReversedSequentailAccessIterator& other)
{
	this->pIterator = new TSequentialAccessIterator(*other.pIterator);
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::~ReversedSequentailAccessIterator()
{
	delete this->pIterator;
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>& ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator++() noexcept
{
	--(*this->pIterator);
	return *this;
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>& ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator--() noexcept
{
	++(*this->pIterator);
	return *this;
}

template<typename TSequentialAccessIterator>
bool ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator==(const ReversedSequentailAccessIterator& other) const noexcept
{
	return *this->pIterator == *other.pIterator;
}

template<typename TSequentialAccessIterator>
bool ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator!=(const ReversedSequentailAccessIterator& other) const noexcept
{
	return *this->pIterator != *other.pIterator;
}

template<typename TSequentialAccessIterator>
typename ReversedSequentailAccessIterator<TSequentialAccessIterator>::ValueType& ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator*()
{
	return *(*this->pIterator);
}

template<typename TSequentialAccessIterator>
typename ReversedSequentailAccessIterator<TSequentialAccessIterator>::ValueType* ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator->()
{
	return (*this->pIterator).operator->();
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator TSequentialAccessIterator()
{
	return *this->pIterator;
}


// 将一个随机访问迭代器包装成反向迭代器
template<typename TRandomAccessIterator>
class ReversedRandomAccessIterator
{
private:
	TRandomAccessIterator* pIterator;
public:
	ReversedRandomAccessIterator(TRandomAccessIterator& it);
	ReversedRandomAccessIterator(const ReversedRandomAccessIterator& other);
	~ReversedRandomAccessIterator();
public:
	using ValueType = typename TRandomAccessIterator::ValueType;
	// 前置++
	ReversedRandomAccessIterator& operator++() noexcept;
	// 前置--
	ReversedRandomAccessIterator& operator--() noexcept;
	// 随机访问
	ReversedRandomAccessIterator operator+(int offset) noexcept;
	ReversedRandomAccessIterator operator-(int offset) noexcept;
	bool operator==(const ReversedRandomAccessIterator& other) const noexcept;
	bool operator!=(const ReversedRandomAccessIterator& other) const noexcept;
	ValueType& operator*();
	ValueType* operator->();
	operator TRandomAccessIterator();
};

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::ReversedRandomAccessIterator(TRandomAccessIterator& it)
{
	this->pIterator = new TRandomAccessIterator(it);
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::ReversedRandomAccessIterator(const ReversedRandomAccessIterator& other)
{
	this->pIterator = new TRandomAccessIterator(*other.pIterator);
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::~ReversedRandomAccessIterator()
{
	delete this->pIterator;
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>& ReversedRandomAccessIterator<TRandomAccessIterator>::operator++() noexcept
{
	--(*this->pIterator);
	return *this;
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>& ReversedRandomAccessIterator<TRandomAccessIterator>::operator--() noexcept
{
	++(*this->pIterator);
	return *this;
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator> ReversedRandomAccessIterator<TRandomAccessIterator>::operator+(int offset) noexcept
{
	TRandomAccessIterator it((*this->pIterator) - offset);
	return ReversedRandomAccessIterator(it);
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator> ReversedRandomAccessIterator<TRandomAccessIterator>::operator-(int offset) noexcept
{
	TRandomAccessIterator it((*this->pIterator) + offset);
	return ReversedRandomAccessIterator(it);
}

template<typename TRandomAccessIterator>
bool ReversedRandomAccessIterator<TRandomAccessIterator>::operator==(const ReversedRandomAccessIterator& other) const noexcept
{
	return *this->pIterator == *other.pIterator;
}

template<typename TRandomAccessIterator>
bool ReversedRandomAccessIterator<TRandomAccessIterator>::operator!=(const ReversedRandomAccessIterator& other) const noexcept
{
	return *this->pIterator != *other.pIterator;
}

template<typename TRandomAccessIterator>
typename ReversedRandomAccessIterator<TRandomAccessIterator>::ValueType& ReversedRandomAccessIterator<TRandomAccessIterator>::operator*()
{
	return *(*this->pIterator);
}

template<typename TRandomAccessIterator>
typename ReversedRandomAccessIterator<TRandomAccessIterator>::ValueType* ReversedRandomAccessIterator<TRandomAccessIterator>::operator->()
{
	return (*this->pIterator).operator->();
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::operator TRandomAccessIterator()
{
	return *this->pIterator;
}



#endif // !REVERSED_ITERATOR


template<typename TValue>
class LinkedList
{
private:
	class LinkedListNode
	{
	public:
		TValue Value;
		LinkedListNode* Previous;
		LinkedListNode* Next;
	};
public:
	using ValueType = TValue;
	// 构造一个空的LinkedList，不含元素
	LinkedList();
	// 构造一个具有n个节点的链表，并初始化为指定的值
	LinkedList(int num, TValue defaultValue);
	// 使用一个范围进行构造，包括begin但不包括end
	template<typename TIterator>
	LinkedList(TIterator beginIt, TIterator endIt);
	// 析构
	~LinkedList();
	// 复制
	LinkedList(LinkedList& other);
	// 移动
	LinkedList(LinkedList&& other);
	// 赋值
	LinkedList& operator=(LinkedList& other);
	LinkedList& operator=(LinkedList&& other);
	class LinkedListIterator;
	using ReversedLinkedListIterator = ReversedSequentailAccessIterator<LinkedListIterator>;
	class LinkedListIterator
	{
	public:
		using ValueType = TValue;
		// 前置++, 使用前需要保证不是End(), 否则结果是未定义的, 后面类似
		LinkedListIterator& operator++() noexcept;
		// 前置--
		LinkedListIterator& operator--() noexcept;
		bool operator==(const LinkedListIterator& other) const noexcept;
		bool operator!=(const LinkedListIterator& other) const noexcept;
		TValue& operator*();
		TValue* operator->();
		operator ReversedLinkedListIterator();
		LinkedListIterator(ReversedLinkedListIterator& rIt);
	private:
		friend class LinkedList;
		LinkedListIterator(LinkedListNode* pItem);
		LinkedListNode* pItem;
	};
public:
	// 获取迭代器
	LinkedListIterator Begin();
	LinkedListIterator End();
	ReversedLinkedListIterator ReversedBegin();
	ReversedLinkedListIterator ReversedEnd();
	// 在it之前插入value, 并且返回指向插入的值的iterator
	LinkedListIterator Insert(TValue& value, LinkedListIterator&& it);
	LinkedListIterator Insert(TValue& value, LinkedListIterator& it);
	// 移除it, 并且返回it原先的后继iterator
	LinkedListIterator Remove(LinkedListIterator&& it);
	LinkedListIterator Remove(LinkedListIterator& it);
	// 查找value, 并且返回指向value的iterator, 如果找不到则返回End()
	template<typename TComparator>
	LinkedListIterator Find(TValue value, TComparator comparator);
	int Count();
private:
	LinkedListNode* pHead;
	LinkedListNode* pTail;
	int count;
};

template<typename TValue>
LinkedList<TValue>::LinkedList()
{
	this->pHead = new LinkedListNode();
	this->pTail = new LinkedListNode();
	this->pHead->Next = this->pTail;
	this->pHead->Previous = nullptr;
	this->pTail->Next = nullptr;
	this->pTail->Previous = this->pHead;
	this->count = 0;
}

template<typename TValue>
LinkedList<TValue>::LinkedList(int num, TValue defaultValue)
{
	this->pHead = new LinkedListNode();
	this->pTail = new LinkedListNode();
	this->pHead->Next = this->pTail;
	this->pHead->Previous = nullptr;
	this->pTail->Next = nullptr;
	this->pTail->Previous = this->pHead;
	this->count = 0;
	for (int i = 0; i < num; i++)
	{
		this->Insert(defaultValue, this->Begin());
	}
}

template<typename TValue>
LinkedList<TValue>::~LinkedList()
{
	LinkedListNode* follow = this->pHead;
	LinkedListNode* ahead = follow;
	while (ahead != nullptr)
	{
		ahead = ahead->Next;
		delete follow;
		follow = ahead;
	}
}

template<typename TValue>
LinkedList<TValue>::LinkedList(LinkedList& other)
{
	this->pHead = new LinkedListNode();
	this->pTail = new LinkedListNode();
	this->pHead->Next = this->pTail;
	this->pHead->Previous = nullptr;
	this->pTail->Next = nullptr;
	this->pTail->Previous = this->pHead;
	this->count = 0;
	for (auto it = other.Begin(); it != other.End(); ++it)
	{
		TValue item = *it;
		this->Insert(item, this->End());
	}
}

template<typename TValue>
LinkedList<TValue>::LinkedList(LinkedList&& other)
{
	this->pHead = other.pHead;
	this->pTail = other.pTail;
	this->count = other.count;
	other.pHead = other.pTail = nullptr;
	other.count = 0;
}

template<typename TValue>
template<typename TIterator>
LinkedList<TValue>::LinkedList(TIterator beginIt, TIterator endIt)
{
	this->pHead = new LinkedListNode();
	this->pTail = new LinkedListNode();
	this->pHead->Next = this->pTail;
	this->pHead->Previous = nullptr;
	this->pTail->Next = nullptr;
	this->pTail->Previous = this->pHead;
	this->count = 0;
	for (auto i = beginIt; i != endIt; ++i)
	{
		TValue value = *i;
		this->Insert(value, this->End());
	}
}

template<typename TValue>
LinkedList<TValue>& LinkedList<TValue>::operator=(LinkedList& other)
{
	LinkedListNode* follow = this->pHead;
	LinkedListNode* ahead = follow;
	while (ahead != nullptr)
	{
		ahead = ahead->Next;
		delete follow;
		follow = ahead;
	}

	this->pHead = new LinkedListNode();
	this->pTail = new LinkedListNode();
	this->pHead->Next = this->pTail;
	this->pHead->Previous = nullptr;
	this->pTail->Next = nullptr;
	this->pTail->Previous = this->pHead;
	this->count = 0;
	for (auto it = other.Begin(); it != other.End(); ++it)
	{
		TValue item = *it;
		this->Insert(item, this->End());
	}
	return *this;
}

template<typename TValue>
LinkedList<TValue>& LinkedList<TValue>::operator=(LinkedList&& other)
{
	LinkedListNode* follow = this->pHead;
	LinkedListNode* ahead = follow;
	while (ahead != nullptr)
	{
		ahead = ahead->Next;
		delete follow;
		follow = ahead;
	}

	this->pHead = other.pHead;
	this->pTail = other.pTail;
	this->count = other.count;
	other.pHead = other.pTail = nullptr;
	other.count = 0;
	return *this;
}

template<typename TValue>
typename LinkedList<TValue>::LinkedListIterator LinkedList<TValue>::Begin()
{
	return LinkedList<TValue>::LinkedListIterator(this->pHead->Next);
}

template<typename TValue>
typename LinkedList<TValue>::LinkedListIterator LinkedList<TValue>::End()
{
	return LinkedList<TValue>::LinkedListIterator(this->pTail);
}

template<typename TValue>
typename LinkedList<TValue>::ReversedLinkedListIterator LinkedList<TValue>::ReversedBegin()
{
	LinkedListIterator rbegin(this->pTail->Previous);
	return LinkedList<TValue>::ReversedLinkedListIterator(rbegin);
}

template<typename TValue>
typename LinkedList<TValue>::ReversedLinkedListIterator LinkedList<TValue>::ReversedEnd()
{
	LinkedListIterator rend(this->pHead);
	return LinkedList<TValue>::ReversedLinkedListIterator(rend);
}

template<typename TValue>
typename LinkedList<TValue>::LinkedListIterator LinkedList<TValue>::Insert(TValue& value, LinkedListIterator&& it)
{
	LinkedListNode* pre = it.pItem->Previous;
	LinkedListNode* next = it.pItem;
	LinkedListNode* node = new LinkedListNode();
	node->Value = value;
	node->Next = next;
	node->Previous = pre;
	pre->Next = node;
	next->Previous = node;
	this->count++;
	return LinkedListIterator(node);

}

template<typename TValue>
typename LinkedList<TValue>::LinkedListIterator LinkedList<TValue>::Insert(TValue& value, LinkedListIterator& it)
{
	LinkedListNode* pre = it.pItem->Previous;
	LinkedListNode* next = it.pItem;
	LinkedListNode* node = new LinkedListNode();
	node->Value = value;
	node->Next = next;
	node->Previous = pre;
	pre->Next = node;
	next->Previous = node;
	this->count++;
	return LinkedListIterator(node);
}

template<typename TValue>
typename LinkedList<TValue>::LinkedListIterator LinkedList<TValue>::Remove(LinkedListIterator&& it)
{
	LinkedListNode* current = it.pItem;
	LinkedListNode* next = current->Next;
	LinkedListNode* pre = current->Previous;
	pre->Next = current->Next;
	next->Previous = current->Previous;
	delete current;
	this->count--;
	return LinkedListIterator(next);
}

template<typename TValue>
typename LinkedList<TValue>::LinkedListIterator LinkedList<TValue>::Remove(LinkedListIterator& it)
{
	LinkedListNode* current = it.pItem;
	LinkedListNode* next = current->Next;
	LinkedListNode* pre = current->Previous;
	pre->Next = current->Next;
	next->Previous = current->Previous;
	delete current;
	this->count--;
	return LinkedListIterator(next);
}

template<typename TValue>
int LinkedList<TValue>::Count()
{
	return this->count;
}


template<typename TValue>
template<typename TComparator>
typename LinkedList<TValue>::LinkedListIterator LinkedList<TValue>::Find(TValue value, TComparator comparator)
{
	for (auto i = this->Begin(); i != this->End(); ++i)
	{
		if (comparator(value, *i) == 0)
		{
			return i;
		}
	}
	return this->End();
}

template<typename TValue>
typename LinkedList<TValue>::LinkedListIterator& LinkedList<TValue>::LinkedListIterator::operator++() noexcept
{
	this->pItem = this->pItem->Next;
	return *this;
}

template<typename TValue>
typename LinkedList<TValue>::LinkedListIterator& LinkedList<TValue>::LinkedListIterator::operator--() noexcept
{
	this->pItem = this->pItem->Previous;
	return *this;
}

template<typename TValue>
bool LinkedList<TValue>::LinkedListIterator::operator==(const LinkedListIterator& other) const noexcept
{
	return this->pItem == other.pItem;
}

template<typename TValue>
bool LinkedList<TValue>::LinkedListIterator::operator!=(const LinkedListIterator& other) const noexcept
{
	return this->pItem != other.pItem;
}

template<typename TValue>
TValue& LinkedList<TValue>::LinkedListIterator::operator*()
{
	return this->pItem->Value;
}

template<typename TValue>
TValue* LinkedList<TValue>::LinkedListIterator::operator->()
{
	return &this->pItem->Value;
}

template<typename TValue>
LinkedList<TValue>::LinkedListIterator::operator ReversedLinkedListIterator()
{
	ReversedLinkedListIterator rIt(*this);
	return rIt;
}

template<typename TValue>
LinkedList<TValue>::LinkedListIterator::LinkedListIterator(ReversedLinkedListIterator& rIt)
{
	this->pItem = ((LinkedListIterator)rIt).pItem;
}

template<typename TValue>
LinkedList<TValue>::LinkedListIterator::LinkedListIterator(LinkedListNode* pItem)
{
	this->pItem = pItem;
}


template<typename TContainer>
class Stack
{
public:
	using ValueType = typename TContainer::ValueType;
	using ExceptionType = int;
	static constexpr int NoCapacityLimit = -1;
	static constexpr ExceptionType StackEmpty = -1;
	static constexpr ExceptionType StackFull = -2;
public:
	// 建立一个指定最大容量的空栈，默认为无限制
	Stack(int capacity = NoCapacityLimit);
	// 禁用拷贝和移动构造
	Stack(const Stack&) = delete;
	Stack(Stack&&) = delete;
	// 获取栈内元素数量
	int Count();
	// 出栈并返回出栈的元素
	ValueType Pop();
	// 返回栈顶元素的引用
	ValueType& Peak();
	// 入栈
	void Push(ValueType& value);

private:
	TContainer container;
	int capacity;
};

template<typename TContainer>
Stack<TContainer>::Stack(int capacity)
{
	this->capacity = capacity;
}

template<typename TContainer>
int Stack<TContainer>::Count()
{
	return this->container.Count();
}

template<typename TContainer>
typename Stack<TContainer>::ValueType Stack<TContainer>::Pop()
{
	if (this->Count() == 0)
	{
		throw StackEmpty;
	}
	ValueType value = *(this->container.ReversedBegin());
	this->container.Remove(this->container.ReversedBegin());
	return value;
}

template<typename TContainer>
typename Stack<TContainer>::ValueType& Stack<TContainer>::Peak()
{
	if (this->Count() == 0)
	{
		throw StackEmpty;
	}
	return *(this->container.ReversedBegin());
}

template<typename TContainer>
void Stack<TContainer>::Push(ValueType& value)
{
	if (this->Count() == this->capacity)
	{
		throw StackFull;
	}
	this->container.Insert(value, this->container.End());
}



#include <iostream>
#include <string>

int main()
{
	int capacity;
	std::cin >> capacity;
	Stack<LinkedList<int>> stack(capacity);

	while (true)
	{
		std::string cmd;
		std::cin >> cmd;
		if (cmd == "quit")
		{
			while (stack.Count() > 0)
			{
				std::cout << stack.Pop() << " ";
			}
			break;
		}
		if (cmd == "pop")
		{
			try
			{
				int val = stack.Pop();
				std::cout << val << std::endl;
			}
			catch (decltype(stack)::ExceptionType e)
			{
				std::cout << "Stack is Empty\n";
			}
		}
		if (cmd == "push")
		{
			int val;
			std::cin >> val;
			try
			{
				stack.Push(val);
			}
			catch (decltype(stack)::ExceptionType e)
			{
				std::cout << "Stack is Full\n";
			}
		}
	}

	return 0;
}